Masala #0840

Abduqodirda $n$ soni bor va bu sonda ‘0’ umuman qatnashmagan. Bu son ustida u quyidagi amalni istalgancha amalga oshirishi mumkin:

• Uzunligi $l$ bo’lgan prefiks olishi (yoki chapdagi birinchi $l$ ta sonni olishi) va uni teskarisiga aylantirishi mumkin. Shunday qilib, eng chapdagi son $l$ – o’rinda turgan son bilan o’rin almashadi, ikki son esa $l-1$ – o’rinda turgan son bilan. Agar son $n = 123456789$ va $l=5$ bo’lsa unda sonning yangi qiymati $543216789$ ga teng bo’ladi.

$l$ ning qiymati har bir operatsiya uchun turlicha bo’lishi mumkin va hatto u n ga teng bo’lishi ham mumkin.

Abduqodir juft sonlarni yaxshi ko’radi. Shu sababdan ham u $n$ sonini yuqoridagi operatsiyalarni bajargan holda juft qilmoqchi, Ammo u bu ishni iloji boricha kamroq urinishlar bilan bajarmoqchi.

Abduqodirga $n$ sonini eng kamida nechta urinishda juft qilish mumkinligini topishda yordam bering yoki bunday qilishning iloji yo’qligini ayting.

Siz $t$ ta so’rovga javob berishingiz kerak. 

Birinchi qatorda sizga $t$ soni beriladi. $(1 ≤ t ≤ 100000)$

Keyingi $t$ ta qatorning har birida sizga bitta son – n soni beriladi $(1 ≤ n < 10^9)$

$T$ ta qatorning har birida shu qatorga mos keladigan so’rovning qiymatini – shu sonni juft qilish uchun kerak bo’ladigan minimal urinishlar sonini chiqaring, agar buning iloji bo’lmasa $-1$ chiqaring.